package com.xy6.struct.graph;

/**
 * Floyd算法，图中多源最短路径求解
 * <pre>
 * 输出每个节点与其他节点的最短距离
 * 首先初始化距离矩阵，然后从第一个点开始逐渐更新矩阵点值。
 * d[i][j]表示从i点到j点的距离。
 * 第k次更新时，判断d[i][k]+d[k][j]与d[i][j]的大小，如果前者小，则更新这个值，否则不变。
 * </pre>
 * 
 * @author zhang
 * @since 2017-10-05
 */
public class Floyd {
	
	/** 邻接矩阵 */
	int[][] Matrix;
	
	/** 顶点 */
	char[] Nodes;

	private final int INF = Integer.MAX_VALUE;

	public Floyd(char[] Nodes, int[][] Matrix) {
		this.Nodes = Nodes;
		this.Matrix = Matrix;
	}

	public void floyd() {
		int[][] distance = new int[Nodes.length][Nodes.length];

		// 初始化距离矩阵
		for (int i = 0; i < Nodes.length; i++) {
			for (int j = 0; j < Nodes.length; j++) {
				distance[i][j] = Matrix[i][j];
			}
		}

		//循环更新矩阵的值
		for (int k = 0; k < Nodes.length; k++) {
			for (int i = 0; i < Nodes.length; i++) {
				for (int j = 0; j < Nodes.length; j++) {
					int temp = (distance[i][k] == INF || distance[k][j] == INF) ? INF : distance[i][k] + distance[k][j];
					if (distance[i][j] > temp) {
						distance[i][j] = temp;
					}
				}
			}
		}

		// 打印floyd最短路径的结果
		System.out.printf("floyd: \n");
		for (int i = 0; i < Nodes.length; i++) {
			for (int j = 0; j < Nodes.length; j++)
				System.out.printf("%12d  ", distance[i][j]);
			System.out.printf("\n");
		}
	}

}
